package algorithm.leetcode;

import algorithm.templates.ListNode;

import java.util.ArrayList;
import java.util.List;

public class NO148_排序链表 {
    class Solution {
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }

            List<Integer> data = new ArrayList<>();
            for (; head != null; head = head.next) {
                data.add(head.val);
            }
            data.sort(Integer::compare);

            ListNode dummy = new ListNode(-1);
            final ListNode[] cur = {dummy};

            data.forEach(e -> {
                ListNode next = new ListNode(e);
                cur[0].next = next;
                cur[0] = next;
            });
            return dummy.next;
        }
    }
}
